import bisect
from functools import cache
from typing import *


class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:

        def dp(num: int):
            @cache
            def f(index, cnt, limit):
                if index == -1:
                    return cnt
                cur = (num >> index) & 1
                u = 1 if not limit else cur
                ans = 0
                for i in range(u + 1):
                    ans += f(
                        index - 1,
                        cnt + (i == 1 and ((index + 1) % x == 0)),
                        limit and i == cur,
                    )
                return ans

            return f(num.bit_length() - 1, 0, True)

        # l, r = 0, (k + 1) << x
        # while l < r:
        #     m = ((r - l) >> 1) + l
        #     if dp(m) <= k:
        #         l = m + 1
        #     else:
        #         r = m
        # return l - 1
        return bisect.bisect_right(range((k + 1) << x), k, key=lambda a: dp(a)) - 1


s = Solution()
print(s.findMaximumNumber(9, 1))
#      0   0
#      1   1
#     10   2
#     11   3
#    100   4
#    101   5
#    110   6
#    111   7
#   1000   8
#   1001   9
#   1010   10
#   1011   11
#   1100   12
#   1101   13
#   1110   14
#   1111   15
#  10000   16
#  10001   17
#  10010   18
#  10011   19


num = 10


@cache
def f(index, cnt, limit):
    if index == -1:
        return cnt
    cur = num >> index & 1
    u = 1 if not limit else cur
    ans = 0
    for i in range(u + 1):
        ans += f(index - 1, cnt + (i == 1 and index == 1), limit and i == cur)
    return ans


a = [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5]
print(list(enumerate(a)))
print(bisect.bisect_left(a, 3))
print(bisect.bisect_right(a, 3))

# print(f(3, 0, True))
